Hóa thạch đầu tiên được phát hiện là một cặp chi trước rất lớn với vài mảnh xương sườn và đốt sống. Chúng được tìm thấy ngày 9 tháng 7 năm 1965 trong cuộc thám hiểm hỗn hợp Ba Lan-Mông Cổ tại Gobi do giáo sư Zofia Kielan-Jaworowska chỉ huy tại di chỉ Altan Ula III thuộc tỉnh Ömnögovi. Kết quả được Kielan-Jaworowska công bố năm 1966.[3]

Deinocheirus được Halszka Osmólska và Ewa Roniewicz đặt tên năm 1970.[2] Loài điển hình và loài duy nhất được đặt tên là Deinocheirus mirificus. Tên chi xuất phát từ tiếng Hy Lạp deinos (δεινός), nghĩa là "khủng kiếp", và cheir (χείρ), nghĩa là "tay". Tên loài (mirificus) từ tiếng Latin, nghĩa là "khác thường" hay "kỳ lạ", từ này được chọn vì "cấu trúc khác thường của chi trước."[2]

Mẫu gốc, ZPal MgD-I/6, được phát hiện ở lớp sa thạch sa mạc có niên đại đầu Maastricht. Nó gồm một bộ xương rời từng mảnh và không toàn vẹn, hầu hết các phần đã bị thời tiết bào mòn khi phát hiện. Cả hai chi trước trừ các vuốt phải, xương đai vai hoàn chỉnh, các thể trung tâm của ba đốt sống, năm xương sườn, xương sườn bụng, và hai xương mang sừng - các xương đỡ cổ, đều có thể phục hồi được.[2]

Các hóa thạch bổ sung, bao gồm các đoạn xương sườn bụng của cùng mẫu vật này, được tìm thấy sau này khi các dội tái kiểm tra địa điểm phát hiện. Một vài đoạn xương này có các vết cắn của loài khủng long bạo chúa đương thời là Tarbosaurus bataar và chỉ ra chứng cứ phù hợp với việc ăn xác chết. Có thể xác Deinocheirus bị Tarbosaurus ăn, điều này giải thích vì sao hóa thạch lại ở trạng thái rời rạc như vậy.[4]

Năm 2014, các nhà cổ sinh vật học mô tả thêm hai mẫu vật Deinocheirus phát hiện năm 2006 và 2009 ở Mông Cổ. Một mẫu vật, MPC-D 100/127, lớn hơn cả mẫu gốc, với chi trước bên trái dài hơn 6%.[1] MPC-D 100/128 lại nhỏ hơn, cả hai mẫu vật mới cho một bộ xương gần như hoàn chỉnh.[5] Các tay săn hóa thạch trộm đã phát hiện hai bộ hóa thạch này. Xương hộp sọ và chân MPC-D 100/127 bị bán ở Nhật Bản, sau đó bán lại ở Đức. Năm 2011, nhà buôn hóa thạch người Pháp François Escuillé kiếm được chúng và tặng cho Viện Khoa học tự nhiên Hoàng gia Bỉ và chúng được trả về Mông Cổ vào tháng 5 năm 2014.[6][7]